/*-----------------------------------------------------------------------------
 * @file  list.h
 * @brief A double (forward and backward) linked list using pointers.
 * @see http://en.wikipedia.org/wiki/Linked_list
    Example:
        @code
        No items in list:
        [first = NULL] [last = NULL]

        One item in list:
        [first] -> [prev = NULL][next = NULL] <- [last]

        Two items in list:
        [first] -> [prev = NULL][next] <-> [prev][next = NULL]  <- [last]

        Three items in list:
        [first] -> [prev = NULL][next] <-> [prev][next] <-> [prev][next = NULL]  <- [last]
        @endcode
-----------------------------------------------------------------------------*/
#ifndef LIST_H
#define LIST_H

#include "globaldef.h"

BEGIN_DECLS

struct list_item_s;
/* Link structure that must be at the head of each item in the list */
typedef struct list_item_s
{
    struct list_item_s* next_item;
    struct list_item_s* prev_item;
} list_item_t;

/* Linked list structure */
typedef struct list_s
{
    struct list_item_s* first_item; /* Pointer to first item in the list */
    struct list_item_s* last_item;  /* Pointer to last item in the list */
    size_t nr_of_items;             /* Counter for number of items in the list */
    size_t max_nr_of_items;         /* Maximum number of items allowed in list; 0 means no limit */
} list_t;

/*-----------------------------------------------------------------------------
 * public functions
 ----------------------------------------------------------------------------*/
/**
 * @brief Initialises a linked list structure
 * @param list              Pointer to the linked list
 * @param max_nr_of_items   Maximum number of items allowed in list; 0 means no limit
 */
void list_init(list_t* list, size_t max_nr_of_items);

/**
 * @brief Initialises a list item.
 * Initialises the item structure to indicate that it is not in the list.
 * @sa list_item_in_list()
 * @param item      Pointer to specified item
 */
void list_item_init(list_item_t* item);

/**
 * @brief See if the list is empty
 * @param list      Pointer to the linked list
 * @return TRUE     List is empty
 * @return FALSE    List contains one or more items
 */
bool list_is_empty(list_t* list);

/**
 * @brief See if the list is full
 * @param list      Pointer to the linked list
 * @retval TRUE     The list is full
 * @retval FALSE    The list is not full, or there is no limit (max_nr_of_items = 0)
 */
bool list_is_full(list_t* list);

/**
 * @brief Get the number of items in the list
 * @param list         Pointer to the linked list
 * @returns size_t     The number of items in the list
 */
size_t list_nr_of_items(list_t* list);

/**
 * @brief Get a pointer to the first item in the list
 * @param list              Pointer to the linked list
 * @returns list_item_t*    Pointer to the first item in the list;
                            NULL will be returned if the list is empty.
 */
list_item_t* list_first_item(list_t* list);

/**
 * @brief Get a pointer to the last item in the list
 * @param list              Pointer to the linked list
 * @returns list_item_t*    Pointer to the last item in the list;
                            NULL will be returned if the list is empty.
 */
list_item_t* list_last_item(list_t* list);

/**
 * @brief Get a pointer to the next item in the list (after the specified item).
 * @param item              Current item
 * @returns list_item_t*    Pointer to the next item in the list;
                            NULL will be returned if the specified item is the
                            last one in the list.
 */
list_item_t* list_next_item(list_item_t* item);

/**
 * @brief Get a pointer to the previous item in the list (before the specified item).
 * @param item              Current item
 * @returns list_item_t*    Pointer to the next item in the list;
                            NULL will be returned if the specified item is the
                            first one in the list.
 */
list_item_t* list_prev_item(list_item_t* item);

/**
 * @brief Insert item to the start of the list.
 * @param list      Pointer to the linked list
 * @param item      Item to be inserted
 * @retval TRUE     Item has been inserted
 * @retval FALSE    List is full
 */
bool list_add_to_start(list_t* list, list_item_t* item);

/**
 * @brief Insert item to before of the item.
 * @param list      Pointer to the linked list
 * @param ref_item  the reference item
 * @param item      Item to be inserted
 * @retval TRUE     Item has been inserted
 * @retval FALSE    List is full
 */
bool list_add_before(list_t* list, list_item_t* ref_item, list_item_t* item);

/**
 * @brief Add item to the end of the list.
 * @param list      Pointer to the linked list
 * @param item      Item to be inserted
 * @retval TRUE     Item has been inserted
 * @retval FALSE    List is full
 */
bool list_add_to_end(list_t* list, list_item_t* item);

/**
 * @brief Add item to the after of item.
 * @param list      Pointer to the linked list
 * @param ref_item  the reference item
 * @param item      Item to be inserted
 * @retval TRUE     Item has been inserted
 * @retval FALSE    List is full
 */
bool list_add_after(list_t* list, list_item_t* ref_item, list_item_t* item);

/**
 * @brief Remove first item from the list
 * @param list      Pointer to the linked list
 * @return list_item_t* Pointer to the (old) first item;
                        NULL will be returned if the list is empty.
 */
list_item_t* list_remove_first_item(list_t* list);

/**
 * @brief Remove last item from the list
 * @param list      Pointer to the linked list
 * @return list_item_t* Pointer to the (old) last item;
                        NULL will be returned if the list is empty.
 */
list_item_t* list_remove_last_item(list_t* list);

/**
 * @brief Remove item from the list
 * @param list      Pointer to the linked list
 * @param item      Item to be removed from the list
 */
void list_remove_item(list_t* list, list_item_t* item);

/**
 * @brief See if item is in the list
 * @param list      Pointer to the linked list
 * @param item      Pointer to specified item
 * @retval TRUE     Item is in the list
 * @retval FALSE    Item is not in the list
 */
bool list_item_in_list(list_t* list, list_item_t* item);

END_DECLS

#endif //~LIST_H
